Методы сортировки и поиска

Сортировка данных с целью организации их в удобном для обработки порядке - настолько важная функция (и даже своего рода искусство) в мире программирования, что для ее выполнения разработан целый ряд специальных программ. Теперь программист, занятый разработкой программы, в которой надо произвести сортировку, может не задумываться о деталях ее реализации до тех пор, пока не закончены полностью все остальные части программы, а затем надо просто выбрать наиболее подходящий метод сортировки.

Два широко используемых метода. «Метод пузырька» получил свое название потому, что при его использовании некоторые из сортируемых элементов как бы всплывают в списке данных, подобно воздушному пузырьку в стакане воды. Программа, работающая по методу пузырька, просматривает список от начала до конца, сравнивая вначале первый и второй элементы, затем второй и третий и т.д. Если порядок следования двух элементов относительно друг друга оказывается неправильным, то они меняются местами. После того как программа доходит до конца списка, она вновь возвращается к его началу и повторяет такую процедуру до тех пор, пока все элементы не займут правильные места.

В программе, выполняющей сортировку «методом корзин» элементы раскладываются по воображаемым коробкам (или корзинам). Например, если мы делаем сортировку в алфавитном порядке, то для каждой буквы можно назначить свою отдельную корзину. Затем каждая корзина делится на подкорзины, а содержащиеся в ней элементы сортируются так, чтобы каждый попал в свою подкорзину. Иногда для больших списков данных комбинация двух описанных методов может оказаться эффективней, чем каждый из них в отдельности. Вначале весь список сортируется методом корзин, а затем каждая корзина в отдельности упорядочивается методом пузырька.